package ljl.alg.jianzhioffer.round2;

import commons.TreeNode;

public class _55_2_balance_tree {
    
    /**
     * 平衡树，每个子树都要是平衡的，一个参数够了
     *
     * 蒙出来了一版，但是不知道效率如何，高不高？
     *
     * 我这个解法，容易想到，但是包含大量重复计算！
     *
     * 简单题刷了这么久，居然不知道这个最优解法！
     * */
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        boolean leftBalanced = isBalanced(root.left);
        boolean rightBalanced = isBalanced(root.right);
        return leftBalanced && rightBalanced && Math.abs(height(root.left) - height(root.right)) <= 1;
    }
    
    int height(TreeNode root) {
        if (root == null) return 0;
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    
    /**
     * good one
     * */
    static class good_one {
        public boolean isBalanced(TreeNode root) {
            return recur(root) != -1;
        }
        int recur(TreeNode root) {
            if (root == null) return 0;
            int left = recur(root.left);
            if (left == -1) return -1;
            int right = recur(root.right);
            if (right == -1) return -1;
            return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
        }
    }
}
